#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 023. 合并K个升序链表.py
@time: 2022/1/11 13:20
@desc: https://leetcode-cn.com/problems/merge-k-sorted-lists/
> 给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

@解题思路：
    1. 两个两个合并
    2. 第i次合并用时为O(i*n), n为每个链表的最长长度, 总的时间复杂度：O(Σi*n),i从1到k，结果为O(k^2*n), s: O(1)
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def mergeLists(self, head1, head2):
        if not head1 and not head2: return None
        if head1 and not head2: return head1
        if not head1 and head2: return head2
        head = ListNode(0)
        p = head
        p1, p2 = head1, head2
        while p1 and p2:
            if p1.val < p2.val:
                p.next = p1
                p1 = p1.next
            else:
                p.next = p2
                p2 = p2.next
            p = p.next
        if p1: p.next = p1
        if p2: p.next = p2
        return head.next

    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists: return None
        head = lists.pop()
        while lists:
            n_head = lists.pop()
            head = self.mergeLists(head, n_head)
        return head

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution02(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        def merge(l1, l2):
            if not l1 and not l2: return None
            if l1 and not l2: return l1
            if not l1 and l2: return l2
            dummy = ListNode()
            p = dummy
            while l1 and l2:
                if l1.val <= l2.val:
                    p.next = l1
                    l1 = l1.next
                else:
                    p.next = l2
                    l2 = l2.next
                p = p.next
            if l1: p.next = l1
            if l2: p.next = l2
            return dummy.next
        if not lists: return None
        lst1 = None
        while lists:
            lst2 = lists.pop()
            lst1 = merge(lst1, lst2)
        return lst1